// 快速排序
/**
 * 算法描述
    1. 从数列中挑出一个元素，称为"基准"（pivot），
    2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）
        在这个分区结束之后，该基准就处于数列的中间位置这个称为分区（partition）操作
    3. 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序
 * 
 * **/

function quickSort(arr) {
    if (arr.length <= 1) return arr;

    let pivotIndex = Math.floor(arr.length / 2);   // 找到基准
    // splice() 方法通过删除或替换现有元素或者原地添加新的元素来修改数组
    // 并以数组的形式返回
    let pivot = arr.splice(pivotIndex, 1)[0];
    let left = [], right = [];

    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        };
    };

    return quickSort(left).concat([pivot],quickSort(right));
};


const arr = [32, 12, 56, 78, 76, 45, 36];

console.log(quickSort(arr));





